package com.example.demo.leetcode;

import java.util.HashMap;
import java.util.Map;

/**
 * 链接：<a href="https://leetcode.cn/problems/lru-cache/description/?envType=study-plan-v2&envId=top-interview-150">https://leetcode.cn/problems/lru-cache/description/?envType=study-plan-v2&envId=top-interview-150</a>
 *
 * @author WangYX
 * @version 1.0.0
 * @date 2024/02/04 14:58
 */
public class _146_LRU缓存 {

    public static void main(String[] args) {
        LRUCache lruCache = new LRUCache(2);
        lruCache.put(1, 0);
        lruCache.put(2, 2);
        int i = lruCache.get(1);
        System.out.println(i);
        lruCache.put(3, 3);
        int i1 = lruCache.get(2);
        System.out.println(i1);
        lruCache.put(4, 4);
        int i2 = lruCache.get(1);
        System.out.println(i2);
        int i3 = lruCache.get(3);
        System.out.println(i3);
        int i4 = lruCache.get(4);
        System.out.println(i4);
    }

    private static class LRUCache {

        private int capacity = 0;
        private int size = 0;

        private Map<Integer, Node> map = null;

        private Node head = new Node(-1, -1, null, null);
        private Node tail = new Node(-1, -1, null, null);

        public LRUCache(int capacity) {
            this.capacity = capacity;
            this.map = new HashMap<Integer, Node>();
            head.next = tail;
            tail.prev = head;
        }

        public int get(int key) {
            Node node = map.getOrDefault(key, new Node(-1, -1, null, null));
            if (node.val == -1) {
                return -1;
            } else {
                Node prev = node.prev;
                Node next = node.next;

                // 2.把该节点的前一个节点指向该节点的后一个节点
                prev.next = next;
                next.prev = prev;

                // 3.添加元素到链表的头节点
                node.next = head.next;
                head.next.prev = node;

                node.prev = head;
                head.next = node;
            }
            return node.val;
        }

        public void put(int key, int value) {
            Node node = map.getOrDefault(key, new Node(-1, -1, null, null));
            int val = node.val;
            if (val == -1) {
                if (size == capacity) {
                    // 1.链表头部插入元素
                    Node current = new Node(key, value, head.next, head);
                    current.next.prev = current;
                    head.next = current;
                    map.put(key, current);

                    // 2.移除链表的尾部元素
                    Node prev = tail.prev;
                    map.remove(prev.key);

                    prev.prev.next = tail;
                    tail.prev = prev.prev;
                } else {
                    // 添加元素到链表的头节点
                    Node current = new Node(key, value, head.next, head);
                    current.next.prev = current;
                    head.next = current;

                    map.put(key, current);
                    size++;
                }
            } else {
                // 1.节点替换旧值
                node.val = value;

                Node prev = node.prev;
                Node next = node.next;

                // 2.把该节点的前一个节点指向该节点的后一个节点
                prev.next = next;
                next.prev = prev;

                // 3.添加元素到链表的头节点
                node.next = head.next;
                head.next.prev = node;

                node.prev = head;
                head.next = node;
            }
        }

        private class Node {
            private int key;
            private int val;
            private Node next;
            private Node prev;

            public Node(int key, int val, Node next, Node prev) {
                this.key = key;
                this.val = val;
                this.next = next;
                this.prev = prev;
            }
        }
    }

}
